#include <iostream>
#include <vector>
#include <memory>
#include <queue>
#include <unordered_set>
#include <algorithm>
#include <random>
#include <cmath>
#include <functional>
#include <cassert>
#include <cfloat>
#include <stack>
#include <cstring>

using OID_TYPE = long long;
using DIS_TYPE = double;

// 点类
template<typename T>
class Point {
public:
    OID_TYPE oId{};
    T key;

    Point() = default;

    // 类中的 key 保存传递的 key 的所有数据, 是深度拷贝
    explicit Point(const OID_TYPE id, const T &key) : oId(id), key(key) {}

    // 类中的 key 保存传递的 key 的引用地址, 非深度拷贝, 且完美转发: 左值存地址, 右值则转移(深拷贝,原key置空)
    explicit Point(const OID_TYPE id, T &&key) : oId(id), key(std::forward<T>(key)) {}

    Point(const Point<T> &other) {
        oId = other.oId;
        key = other.key;
    }

    Point<T> &operator=(const Point<T> &other) {
        oId = other.oId;
        key = other.key;
        return *this;
    }

    bool operator==(const Point<T> &other) const {
        return oId == other.oId && key == other.key;
    }

    // 按 oid 升序排序
    bool operator<(const Point<T> &other) const {
        return oId < other.oId;
    }

    // 计算距离
    [[nodiscard]] DIS_TYPE distance(const T &otherKey) const {
        return key.distance(otherKey);
    }

    [[nodiscard]] DIS_TYPE distance(const Point<T> &otherPoint) const {
        return key.distance(otherPoint.key);
    }
};

// 叶节点向索引节点递归提取的元素
template<typename T>
class DownUp : public Point<T> {
public:
    DIS_TYPE dis;

    explicit DownUp(const Point<T> &point1, const DIS_TYPE dis = DBL_MAX) : Point<T>(point1), dis(dis) {}

    explicit DownUp(const OID_TYPE id, const T &key, const DIS_TYPE dis = DBL_MAX) : Point<T>(id, key), dis(dis) {}

    explicit DownUp(const OID_TYPE id, T &&key, const DIS_TYPE dis = DBL_MAX) : Point<T>(id, std::forward<T>(key)),
                                                                                dis(dis) {}

    DownUp(const DownUp &other) : Point<T>(other), dis(other.dis) {}
};

// 自定义哈希函数
template<typename T>
class PointHash {
public:
    std::size_t operator()(const Point<T> &point) const {
        std::size_t seed = std::hash<OID_TYPE>()(point.oId);
        seed ^= std::hash<T>()(point.key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

// 自定义相等比较函数
template<typename T>
class PointEqual {
public:
    bool operator()(const Point<T> &lhs, const Point<T> &rhs) const {
        return lhs == rhs;
    }
};

// 点对结构体
struct PointPair {
    OID_TYPE index1, index2;
    DIS_TYPE dis;

    PointPair(OID_TYPE i1, OID_TYPE i2, DIS_TYPE dist) : index1(i1), index2(i2), dis(dist) {}

    // 重载 > 操作符，用于优先队列
    bool operator>(const PointPair &other) const {
        return dis > other.dis;
    }
};

// 树节点基类
template<typename T>
class MLTreeNode {
public:
    MLTreeNode() = default;

    virtual ~MLTreeNode() = default;

    [[nodiscard]] virtual DIS_TYPE area() const = 0;

    virtual void updateCenterAndRadius() = 0;

    [[nodiscard]] virtual std::unique_ptr<MLTreeNode<T>> clone() const = 0;

    virtual void rangeQuery(const Point<T> &queryPoint, DIS_TYPE queryRadius, std::vector<Point<T>> &result) = 0;

    virtual void printNode() const = 0;

    [[nodiscard]] virtual bool isLeaf() const = 0;

    virtual void addEntry(const DownUp<T> &entry) = 0;

    [[nodiscard]] virtual std::unordered_set<Point<T>, PointHash<T>, PointEqual<T>> getPoints() const = 0;

    virtual bool addEntryIfPossible(const DownUp<T> &entry, unsigned long M) = 0;

    [[nodiscard]] virtual Point<T> getCenter() const = 0;

    [[nodiscard]] virtual DIS_TYPE getRadius() const = 0;

};

// 路由对象类
template<typename T>
class RoutingObject {
public:
    static unsigned long n_build_ops;
    Point<T> point;
    std::unique_ptr<MLTreeNode<T>> subtree;
    DIS_TYPE cover_radius{};
    DIS_TYPE dis{};

    RoutingObject() : point(OID_TYPE(), {}), subtree(nullptr), dis(DBL_MAX), cover_radius(DBL_MAX) {}

    explicit RoutingObject(const Point<T> &point1, const DIS_TYPE cr, const DIS_TYPE dis = DBL_MAX)
            : point(point1), subtree(nullptr), cover_radius(cr), dis(dis) {}

    explicit RoutingObject(const OID_TYPE id, const T &key, const DIS_TYPE cr, const DIS_TYPE dis = DBL_MAX)
            : point(id, key), subtree(nullptr), cover_radius(cr), dis(dis) {}

    explicit RoutingObject(const OID_TYPE id, T &&key, const DIS_TYPE cr, const DIS_TYPE dis = DBL_MAX)
            : point(id, std::forward<T>(key)), subtree(nullptr), cover_radius(cr), dis(dis) {}

    [[nodiscard]] DIS_TYPE distance(const T &otherKey) const {
        RoutingObject<T>::n_build_ops++;
        return point.distance(otherKey);
    }

    [[nodiscard]] DIS_TYPE distance(const Point<T> &otherPoint) const {
        RoutingObject<T>::n_build_ops++;
        return point.distance(otherPoint);
    }

    // 显式定义拷贝构造函数
    RoutingObject(const RoutingObject &other)
            : point(other.point),
              subtree(other.subtree ? other.subtree->clone() : nullptr), // 使用克隆方法
              cover_radius(other.cover_radius),
              dis(other.dis) {

        RoutingObject<T>::n_build_ops++;
    }

    RoutingObject &operator=(const RoutingObject &other) {
        if (this != &other) {
            point = other.point;
            dis = other.dis;
            cover_radius = other.cover_radius;
            subtree = other.subtree ? other.subtree->clone() : nullptr;
        }

        return *this;
    }
};

// 数据库条目类
template<typename T>
class DBEntry {
public:
    static unsigned long n_query_ops;

    Point<T> point;
    DIS_TYPE dis{};

    DBEntry() = default;

    explicit DBEntry(const Point<T> &point1, const DIS_TYPE dis = DBL_MAX) : point(point1), dis(dis) {}

    explicit DBEntry(const OID_TYPE id, const T &key, const DIS_TYPE dis = DBL_MAX) : point(id, key), dis(dis) {}

    explicit DBEntry(const OID_TYPE id, T &&key, const DIS_TYPE dis = DBL_MAX) : point(id, std::forward<T>(key)),
                                                                                 dis(dis) {}

    DBEntry(const DBEntry &other) {
        point = other.point;
        dis = other.dis;
    }

    DBEntry &operator=(const DBEntry &other) {
        if (this != &other) {
            point = other.point;
            dis = other.dis;
        }
        return *this;
    }

    [[nodiscard]] DIS_TYPE distance(const T &otherKey) const {
        DBEntry<T>::n_query_ops++;
        return point.distance(otherKey);
    }

    [[nodiscard]] DIS_TYPE distance(const Point<T> &otherPoint) const {
        DBEntry<T>::n_query_ops++;
        return point.distance(otherPoint);
    }
};

// 静态成员变量定义
template<typename T>
unsigned long RoutingObject<T>::n_build_ops = 0;

template<typename T>
unsigned long DBEntry<T>::n_query_ops = 0;

// 内部节点类
template<typename T>
class MTreeInternal : public MLTreeNode<T> {
public:
    Point<T> center;
    DIS_TYPE radius{};
    std::vector<RoutingObject<T>> entries;

    explicit MTreeInternal(std::vector<RoutingObject<T>> &objs) {
        if (!objs.empty()) {
            entries = std::move(objs);
        }
    }

    [[nodiscard]] DIS_TYPE area() const override {
        return M_PI * radius * radius;
    }

    bool operator==(const MTreeInternal<T> &other) const {
        return entries == other.entries && center == other.center && radius == other.radius;
    }

    void updateCenterAndRadius() override {
        if (!entries.empty()) {
            center = entries.back().point;
            radius = 0;
            for (auto &entry: entries) {
                DIS_TYPE dist = center.distance(entry.point);
                entry.dis = dist;
                if (dist > radius) {
                    radius = dist;
                }
            }
        }
    }

    // 显式定义拷贝构造函数
    MTreeInternal(const MTreeInternal<T> &other) : center(other.center), radius(other.radius),
                                                   entries(other.entries) {}

    // 显式定义拷贝赋值操作符
    MTreeInternal<T> &operator=(const MTreeInternal<T> &other) {
        if (this != &other) {
            center = other.center;
            radius = other.radius;
            entries = other.entries;
        }
        return *this;
    }

    [[nodiscard]] std::unique_ptr<MLTreeNode<T>> clone() const override {
        return std::make_unique<MTreeInternal<T>>(*this); // 返回当前类的深拷贝
    }

    void rangeQuery(const Point<T> &queryPoint, DIS_TYPE queryRadius, std::vector<Point<T>> &result) override {
        DIS_TYPE distToCenter = queryPoint.distance(center);
        if (distToCenter > radius + queryRadius) {
            return;
        }
        for (auto &routingObj: entries) {
            if (routingObj.subtree) {
                routingObj.subtree->rangeQuery(queryPoint, queryRadius, result);
            }
        }
    }

    void printNode() const override {
        std::cout << "Internal Node:" << std::endl;
        std::cout << "  Center OID: " << center.oId << "  Radius: " << radius << ", Coordinates: ";
        for (const auto &coord: center.key) {
            std::cout << coord << " ";
        }
        std::cout << std::endl;

        for (const auto &entry: entries) {
            std::cout << "  Routing Object OID: " << entry.point.oId << ", Coordinates: ";
            for (const auto &coord: entry.point.key) {
                std::cout << coord << " ";
            }
            std::cout << std::endl;

            if (entry.subtree) {
                entry.subtree->printNode();
            }
        }
    }

    [[nodiscard]] bool isLeaf() const override {
        return false;
    }

    [[nodiscard]] std::unordered_set<Point<T>, PointHash<T>, PointEqual<T>> getPoints() const override {
        std::unordered_set<Point<T>, PointHash<T>, PointEqual<T>> nodePoints;
        for (const auto &entry: entries) {
            nodePoints.insert(entry.point);
        }
        return nodePoints;
    }

    void addEntry(const DownUp<T> &entry) override {
        entries.emplace_back(entry.oId, entry.key, entry.dis);
    }

    bool addEntryIfPossible(const DownUp<T> &entry, unsigned long M) override {
        if (entries.size() < M) {
            entries.emplace_back(entry.oId, entry.key, entry.dis);
            return true;
        }
        return false;
    }

    [[nodiscard]] Point<T> getCenter() const override {
        return center;
    }

    [[nodiscard]] DIS_TYPE getRadius() const override {
        return radius;
    }
};

// 叶节点类
template<typename T>
class MTreeLeaf : public MLTreeNode<T> {
public:
    std::vector<DBEntry<T>> entries;
    Point<T> center;
    DIS_TYPE radius{};

    explicit MTreeLeaf(std::vector<DBEntry<T>> &objs) {
        if (!objs.empty()) {
            entries = std::move(objs);
        }
    }

    [[nodiscard]] DIS_TYPE area() const override {
        return M_PI * radius * radius;
    }

    bool operator==(const MTreeLeaf<T> &other) const {
        return entries == other.entries && center == other.center && radius == other.radius;
    }

    void addEntry(const DownUp<T> &entry) override {
        DBEntry<T> newEntry(entry.oId, entry.key, entry.dis);
        entries.emplace_back(std::move(newEntry));
    }

    void updateCenterAndRadius() override {
        if (!entries.empty()) {
            center = entries.back().point;
            radius = 0;
            for (auto &entry: entries) {
                DIS_TYPE dist = center.distance(entry.point);
                entry.dis = dist;
                if (dist > radius) {
                    radius = dist;
                }
            }
        }
    }

    // 显式定义拷贝构造函数
    MTreeLeaf(const MTreeLeaf<T> &other) : entries(other.entries), center(other.center), radius(other.radius) {}

    // 显式定义拷贝赋值操作符
    MTreeLeaf<T> &operator=(const MTreeLeaf<T> &other) {
        if (this != &other) {
            entries = other.entries;
            center = other.center;
            radius = other.radius;
        }
        return *this;
    }

    [[nodiscard]] std::unique_ptr<MLTreeNode<T>> clone() const override {
        return std::make_unique<MTreeLeaf<T>>(*this); // 返回当前类的深拷贝
    }

    void rangeQuery(const Point<T> &queryPoint, DIS_TYPE queryRadius, std::vector<Point<T>> &result) override {
        DIS_TYPE distToCenter = queryPoint.distance(center);
        if (distToCenter > radius + queryRadius) {
            return;
        }
        for (const auto &entry: entries) {
            DIS_TYPE distToObj = queryPoint.distance(entry.point);
            if (distToObj <= queryRadius) {
                result.push_back(entry.point);
            }
        }
    }

    void printNode() const override {
        std::cout << "Leaf Node:" << std::endl;
        std::cout << "  Center OID: " << center.oId << "  Radius: " << radius << ", Coordinates: ";
        for (const auto &coord: center.key) {
            std::cout << coord << " ";
        }
        std::cout << std::endl;

        for (const auto &entry: entries) {
            std::cout << "  Entry OID: " << entry.point.oId << ", Coordinates: ";
            for (const auto &coord: entry.point.key) {
                std::cout << coord << " ";
            }
            std::cout << std::endl;
        }
    }

    [[nodiscard]] bool isLeaf() const override {
        return true;
    }

    [[nodiscard]] std::unordered_set<Point<T>, PointHash<T>, PointEqual<T>> getPoints() const override {
        std::unordered_set<Point<T>, PointHash<T>, PointEqual<T>> nodePoints;
        for (const auto &entry: entries) {
            nodePoints.insert(entry.point);
        }
        return nodePoints;
    }

    bool addEntryIfPossible(const DownUp<T> &entry, unsigned long M) override {
        if (entries.size() < M) {
            DBEntry<T> newEntry(entry.oId, entry.key, entry.dis);
            entries.emplace_back(std::move(newEntry));
            return true;
        }
        return false;
    }

    [[nodiscard]] Point<T> getCenter() const override {
        return center;
    }

    [[nodiscard]] DIS_TYPE getRadius() const override {
        return radius;
    }
};

// MLTree类
template<typename T>
class MLTree {
private:
    std::unique_ptr<MLTreeNode<T>> root;

public:
    MLTree() : root(nullptr) {}

    ~MLTree() = default;

    void Clear() {
        root.reset();
    }

    // 打印树的函数
    void printTree() const {
        if (root) {
            root->printNode();
        }
    }

    // 步骤 1：构建候选节点集 E
    std::vector<std::unique_ptr<MLTreeNode<T>>>
    buildCandidateNodes(const std::vector<DownUp<T>> &objects, unsigned long M, bool firstFlag);

    // 步骤 2：选择子集 A
    std::vector<std::unique_ptr<MLTreeNode<T>>>
    selectSubsetA(const std::vector<std::unique_ptr<MLTreeNode<T>>> &E, bool firstFlag);

    // 步骤 3：非递归构建 M-Tree
    void buildMLTree(const std::vector<DownUp<T>> &objects, unsigned long M);

    // 范围查询函数
    void rangeQuery(const Point<T> &queryPoint, DIS_TYPE queryRadius, std::vector<Point<T>> &result);
};

// 步骤 1：构建候选节点集 E
template<typename T>
std::vector<std::unique_ptr<MLTreeNode<T>>>
MLTree<T>::buildCandidateNodes(const std::vector<DownUp<T>> &objects, unsigned long M, bool firstFlag) {
    std::vector<std::unique_ptr<MLTreeNode<T>>> E;
    std::vector<bool> used(objects.size(), false);
    std::priority_queue<PointPair, std::vector<PointPair>, std::greater<>> pq;

    // 构建优先队列
    for (size_t i = 0; i < objects.size(); i++) {
        for (size_t j = i + 1; j < objects.size(); j++) {
            pq.emplace(i, j, objects[i].key.distance(objects[j].key));
        }
    }

    // 处理优先队列
    while (!pq.empty()) {
        auto pair = pq.top();
        pq.pop();

        if (used[pair.index1] && used[pair.index2]) continue;

        bool merged = false, isFlag = true;
        for (auto &node: E) {
            if ((firstFlag && node->isLeaf()) || (!firstFlag && !node->isLeaf())) {
                auto nodePoints = node->getPoints();
                if (nodePoints.find(objects[pair.index1]) != nodePoints.end()) {
                    if (node->addEntryIfPossible(objects[pair.index2], M)) {
                        used[pair.index1] = true;
                        used[pair.index2] = true;
                        merged = true;
                        break;
                    } else {
                        isFlag = false;
                    }
                } else if (nodePoints.find(objects[pair.index2]) != nodePoints.end()) {
                    if (node->addEntryIfPossible(objects[pair.index1], M)) {
                        used[pair.index1] = true;
                        used[pair.index2] = true;
                        merged = true;
                        break;
                    } else {
                        isFlag = false;
                    }
                }
            }
        }

        if (!merged && isFlag) {
            if (firstFlag) {
                std::vector<DBEntry<T>> newEntries;
                newEntries.emplace_back(objects[pair.index1].oId, objects[pair.index1].key);
                newEntries.emplace_back(objects[pair.index2].oId, objects[pair.index2].key);
                E.emplace_back(std::make_unique<MTreeLeaf<T>>(newEntries));
            } else {
                std::vector<RoutingObject<T>> newEntries;
                newEntries.emplace_back(objects[pair.index1].oId, objects[pair.index1].key, objects[pair.index1].dis);
                newEntries.emplace_back(objects[pair.index2].oId, objects[pair.index2].key, objects[pair.index2].dis);
                E.emplace_back(std::make_unique<MTreeInternal<T>>(newEntries));
            }
            used[pair.index1] = true;
            used[pair.index2] = true;
        }
    }

    for (auto &node: E) {
        node->updateCenterAndRadius();
    }

    return E;
}

// 步骤 2：选择子集 A
template<typename T>
std::vector<std::unique_ptr<MLTreeNode<T>>>
MLTree<T>::selectSubsetA(const std::vector<std::unique_ptr<MLTreeNode<T>>> &E, bool firstFlag) {
    std::vector<std::unique_ptr<MLTreeNode<T>>> A;
    std::vector<std::pair<DIS_TYPE, std::unique_ptr<MLTreeNode<T>>>> sortedE;

    // 定义成本函数
    auto cost = [](const MLTreeNode<T> *node) { return node->area(); };

    // 存储节点及其成本
    for (auto &node: E) {
        sortedE.emplace_back(cost(node.get()), node->clone());
    }

    // 根据成本排序
    std::sort(sortedE.begin(), sortedE.end(), [](const auto &a, const auto &b) {
        return a.first < b.first;
    });

    std::unordered_set<Point<T>, PointHash<T>, PointEqual<T>> coveredObjects;
    for (auto &pair: sortedE) {
        if ((firstFlag && pair.second->isLeaf()) || (!firstFlag && !pair.second->isLeaf())) {
            auto newEntries = pair.second->getPoints();
            std::vector<Point<T>> uniqueNewEntries;
            for (const auto &entry: newEntries) {
                if (coveredObjects.find(entry) == coveredObjects.end()) {
                    uniqueNewEntries.push_back(entry);
                }
            }

            int newEntriesCount = uniqueNewEntries.size();
            if (newEntriesCount > 0) {
                double ratio = static_cast<double>(pair.first) / newEntriesCount;
                auto it = A.begin();
                bool inserted = false;
                for (; it != A.end(); ++it) {
                    if ((firstFlag && (*it)->isLeaf()) || (!firstFlag && !(*it)->isLeaf())) {
                        auto currentEntries = (*it)->getPoints();
                        int currentNewEntriesCount = 0;
                        for (const auto &entry: currentEntries) {
                            if (coveredObjects.find(entry) == coveredObjects.end()) {
                                currentNewEntriesCount++;
                            }
                        }
                        double currentRatio = static_cast<double>(cost(it->get())) / currentNewEntriesCount;
                        if (ratio < currentRatio) {
                            A.insert(it, std::move(pair.second));
                            inserted = true;
                            break;
                        }
                    }
                }

                if (!inserted) {
                    A.push_back(std::move(pair.second));
                }

                // 一次性将新对象添加到 coveredObjects 中
                coveredObjects.insert(uniqueNewEntries.begin(), uniqueNewEntries.end());
            }
        }
    }

    return A;
}

// 步骤 3：非递归构建 M-Tree
template<typename T>
void MLTree<T>::buildMLTree(const std::vector<DownUp<T>> &objects, unsigned long M) {
    std::stack<std::vector<DownUp<T>>> objectStack;
    objectStack.push(objects);

    bool firstFlag = true;
    while (!objectStack.empty()) {
        std::vector<DownUp<T>> currentObjects = objectStack.top();
        objectStack.pop();

        std::vector<std::unique_ptr<MLTreeNode<T>>> E = buildCandidateNodes(currentObjects, M, firstFlag);
        std::vector<std::unique_ptr<MLTreeNode<T>>> A = selectSubsetA(E, firstFlag);

        if (firstFlag) {
            firstFlag = false;
            std::vector<DownUp<T>> newObjects;
            std::vector<RoutingObject<T>> routingObjects;

            for (auto &node: A) {
                if (node->isLeaf()) {
                    newObjects.emplace_back(node->getCenter(), node->getRadius());
                    RoutingObject<T> routingObj(node->getCenter(), node->getRadius());
                    routingObj.subtree = std::move(node);
                    routingObjects.emplace_back(std::move(routingObj));
                }
            }
            objectStack.push(newObjects);

            if (!routingObjects.empty()) {
                root = std::make_unique<MTreeInternal<T>>(routingObjects);
                root->updateCenterAndRadius();
            }
        } else {
            if (A.size() == 1) {
                root = std::move(A[0]);
            } else {
                std::vector<DownUp<T>> newObjects;
                std::vector<RoutingObject<T>> routingObjects;

                for (auto &node: A) {
                    if (!node->isLeaf()) {
                        newObjects.emplace_back(node->getCenter(), node->getRadius());
                        RoutingObject<T> routingObj(node->getCenter(), node->getRadius());
                        routingObj.subtree = std::move(node);
                        routingObjects.emplace_back(std::move(routingObj));
                    }
                }
                objectStack.push(newObjects);

                if (!routingObjects.empty()) {
                    auto newInternalNode = std::make_unique<MTreeInternal<T>>(routingObjects);
                    newInternalNode->updateCenterAndRadius();
                    root = std::move(newInternalNode);
                }
            }
        }
    }
}

// 范围查询函数
template<typename T>
void MLTree<T>::rangeQuery(const Point<T> &queryPoint, DIS_TYPE queryRadius, std::vector<Point<T>> &result) {
    if (root) {
        root->rangeQuery(queryPoint, queryRadius, result);
    }
}

static long long m_id = 1;
static std::random_device m_rd;
static std::mt19937_64 m_gen(100ULL);
static std::uniform_real_distribution<double> m_distrib(-1.0, 1.0);
static std::uniform_real_distribution<double> m_eps(-0.03, 0.03);

double Radius = 0.10;

#define KEY_LENGTH 8

class KeyObject {
public:
    std::vector<DIS_TYPE> key;

    KeyObject() : key(KEY_LENGTH, 0.0) {}

    explicit KeyObject(const double keyArr[]) {
        key.assign(keyArr, keyArr + KEY_LENGTH);
    }

    KeyObject(const KeyObject &other) {
        key = other.key;
    }

    KeyObject &operator=(const KeyObject &other) {
        if (this != &other) {
            key = other.key;
        }
        return *this;
    }

    [[nodiscard]] double distance(const KeyObject &other) const {
        double d = 0;
        for (size_t i = 0; i < KEY_LENGTH; i++) {
            d += std::pow(key[i] - other.key[i], 2.0);
        }
        return std::sqrt(d);
    }

    typename std::vector<DIS_TYPE>::iterator begin() {
        return key.begin();
    }

    typename std::vector<DIS_TYPE>::iterator end() {
        return key.end();
    }

    [[nodiscard]] typename std::vector<DIS_TYPE>::const_iterator begin() const {
        return key.begin();
    }

    [[nodiscard]] typename std::vector<DIS_TYPE>::const_iterator end() const {
        return key.end();
    }

    bool operator==(const KeyObject &other) const {
        return key == other.key;
    }

    friend std::size_t hash_value(const KeyObject &obj) {
        std::size_t hashvalue = 0;
        for (const auto &val: obj.key) {
            uint64_t val_as_int;
            std::memcpy(&val_as_int, &val, sizeof(val));
            hashvalue ^= std::hash<uint64_t>()(val_as_int) + 0x9e3779b9 + (hashvalue << 6) + (hashvalue >> 2);
        }
        return hashvalue;
    }
};

namespace std {
    template<>
    struct hash<KeyObject> {
        std::size_t operator()(const KeyObject &obj) const {
            return hash_value(obj);
        }
    };
}

void generate_center(double center[]) {
    for (int i = 0; i < KEY_LENGTH; i++) {
        center[i] = m_distrib(m_gen);
    }
}

uint32_t generate_data(std::vector<DownUp<KeyObject>> &entries, const int N) {
    double buf[KEY_LENGTH];
    for (int i = 0; i < N; i++) {
        generate_center(buf);
        DownUp<KeyObject> entry(m_id++, KeyObject(buf), 0);
        entries.push_back(entry);
    }
    return entries.size();
}

int main() {
    std::cout << "Add Points: " << std::endl;
    const int N = 1000;
    std::vector<DownUp<KeyObject>> entries;
    generate_data(entries, N);
    assert(entries.size() == N);

    unsigned long M = 20;

    auto MLTreePtr = std::make_unique<MLTree<KeyObject>>();
    MLTreePtr->buildMLTree(entries, M);

    std::cout << "\nTree information:" << std::endl;
    MLTreePtr->printTree();

    return 0;
}